On this page you can get a detailed analysis of a word or phrase, produced by the best artificial intelligence technology to date:
В теории графов псевдолес — это неориентированный граф , в котором любая связная компонента имеет максимум один цикл. То есть это система вершин и рёбер, соединяющих пары вершин, такая, что никакие два цикла не имеют общих вершин и не могут быть связаны путём. Псевдодерево — это связный псевдолес.
Названия взяты по аналогии с общеизвестными деревьями и лесами (дерево — это связный граф без циклов, лес — объединение несвязных деревьев). Габов и Тарьян приписывают изучение псевдолесов книге 1963 Данцига по линейному программированию, в которой псевдолеса появляются в решении некоторых задач транспортных потоков. Псевдолеса также образуют теоретические графовые модели функций и появляются в некоторых алгоритмических задачах. Псевдолеса являются разреженными графами – они имеют очень малое число рёбер по отношению к числу вершин, и их структура матроидов позволяет некоторые другие семейства редких графов разложить на объединение лесов и псевдолесов. Название "псевдолес" пришло из статьи Пикарда и Керанна.